/*
欧几里得算法    gcd(a,b) = gcd(b,a%b)
又名【辗转相除】法，迄今为止已知的最古老的算法，距今(2017年)2317年
用于快速计算两个数字的最大公约数，还可以用于快速求解a*x + b*y = 1方程的一组整数解

定理：a和b两个整数的最大公约数等于b与a % b的最大公约数
形式化表示：假设a,b != 0 则，gcd(a,b) = gcd(b, a%b)
证明1:
    1.设 c = gcd(a,b), 则a = cx, b = cy
    2.可知a % b = r = a - k * b = cx - kcy = c(x - ky)
    3.可知c也是r的因数
    4.其中x - ky 与 y 互素， 见证明2
    所以可知：gcd(a, b) = gcd(b, r) = gcd(b, a%b)
证明2：
    1.假设gcd(x - ky, y) = d
    2.则y = nd, x - ky = md,则x = knd + md = d(kn + m)
    3.重新表示a, b, 则有a =  cd(kn + m) = cdn
    4.则可得gcd(a, b) >= cd. 又因为gcd(a, b) = c,所以d = 1
*/
// inline 修饰符并非强制性的：编译器有可能会置之不理。
// 例如，递归函数通常不会被编译成内联函数。编译器有权自行决定是否要将有 inline 修饰符的函数编译成内联函数。
#include <stdio.h>
int my_gcd(int a, int b)
{
    int temp = a;
    while (temp != 0)
    {
        temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}
int gcd(int a, int b)
{
    return (b ? gcd(b, a % b) : a);
}
int main(int argc, char* argv[])
{
    int a, b;
    while(~scanf("%d %d", &a, &b))
    {
        if(a == 0 || b == 0) break;
        printf("gcd(%d, %d) = %d\n", a, b, gcd(a,b));
        printf("my_gcd(%d, %d) = %d\n", a, b, my_gcd(a,b));
    }
    return 0;
}